//给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市
//、目的地城市和你初始拥有的汽油总量 
//
// 每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 
//j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。 
//
// 请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。 
//
// 请你返回从 start 到 finish 所有可能路径的数目。 
//
// 由于答案可能很大， 请将它对 10^9 + 7 取余后返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
//输出：4
//解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
//1 -> 3
//1 -> 2 -> 3
//1 -> 4 -> 3
//1 -> 4 -> 2 -> 3
// 
//
// 示例 2： 
//
// 
//输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
//输出：5
//解释：以下为所有可能的路径：
//1 -> 0，使用汽油量为 fuel = 1
//1 -> 2 -> 0，使用汽油量为 fuel = 5
//1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
//1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
//1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
// 
//
// 示例 3： 
//
// 
//输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
//输出：0
//解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。 
//
// 
//
// 提示： 
//
// 
// 2 <= locations.length <= 100 
// 1 <= locations[i] <= 10⁹ 
// 所有 locations 中的整数 互不相同 。 
// 0 <= start, finish < locations.length 
// 1 <= fuel <= 200 
// 
//
// Related Topics 记忆化搜索 数组 动态规划 👍 113 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Map;

public class CountAllPossibleRoutes {
    public static void main(String[] args) {
        Solution solution = new CountAllPossibleRoutes().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 缓存器 用于记录【特定状态】下的结果
         * cache[i][fuel] 代表位置从i出发 当前油量为fuel的前提下，到达目标位置的路径数量
         */
        int[][] cache;
        int mod = 1000000007;

        /**
         * 任何的记忆化搜索都可以转变为动态规划
         *
         * @param locations
         * @param start
         * @param finish
         * @param fuel
         * @return
         */
        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            int[][] f = new int[n][fuel + 1]; // f[i][j] 表示从下边i开始，并且剩余油量是j的情况下到达目标地方的路径数

            //初始化
            for (int i = 0; i <= fuel; i++) f[finish][i] = 1;

            // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
            // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
            // 其中 i 和 k 并无严格的大小关系
            // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
            // 因此需要先从小到大枚举油量
            for (int curr = 0; curr <= fuel; curr++) {
                //起点
                for (int i = 0; i < n; i++) {
                    //当前起点
                    for (int k = 0; k < n; k++) {
                        if (i!=k){
                            int need = Math.abs(locations[i] - locations[k]);
                            if (curr>=need){
                                f[i][curr] += f[k][curr-need];
                                f[i][curr] %=mod;
                            }
                        }
                    }
                }
            }
            return f[start][fuel];
        }

        /**
         * 记忆化搜索
         *
         * @param locations
         * @param start
         * @param finish
         * @param fuel
         * @return
         */
//        public int countRoutes(int[] locations, int start, int finish, int fuel) {
//            int n = locations.length;
//            cache = new int[n][fuel + 1];
//            for (int i = 0; i < n; i++) {
//                Arrays.fill(cache[i], -1);
//            }
//            return dfs(locations, start, finish, fuel);
//        }

        /**
         * 根据宫水的说法 base case条件可以优化掉
         *
         * @param locations
         * @param curr
         * @param finish
         * @param fuel
         * @return
         */
        private int dfs(int[] locations, int curr, int finish, int fuel) {
            //如果缓存器中已经有答案，直接返回
            if (cache[curr][fuel] != -1) {
                return cache[curr][fuel];
            }
            int n = locations.length;
            /**
             * ⭐️️️⭐️️️⭐️️️ 如果一步都到不了，说明从位置u不能到达end位置
             * 将结果0写入缓存器并返回
             */
            int needCurr = Math.abs(locations[curr] - locations[finish]);
            if (needCurr > fuel) {
                cache[curr][fuel] = 0;
                return 0;
            }
            /**
             * 计算油量为fuel，从位置curr到end的路径数量
             * 由于每个点都可以经过多次如果curr=end 那么本身就算一条路径
             */
            int sum = curr == finish ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != curr) {
                    int need = Math.abs(locations[i] - locations[curr]);
                    if (fuel >= need) {
                        sum += dfs(locations, i, finish, fuel - need);
                        sum %= mod;
                    }
                }
            }
            cache[curr][fuel] = sum;
            return sum;
        }
//        private int dfs(int[] locations, int curr, int finish, int fuel) {
//            //如果缓存器中已经有答案，直接返回
//            if (cache[curr][fuel] != -1) {
//                return cache[curr][fuel];
//            }
//            int n = locations.length;
//            /**
//             * base case 1 :如果油量为0 且不在目标位置
//             * //将0写入缓存起并返回
//             */
//            if (fuel == 0 && curr != finish) {
//                cache[curr][fuel] = 0;
//                return 0;
//            }
//            /**
//             * 油量不为0且无法到达任何位置
//             * 将结果0写入缓存器并且返回
//             */
//            boolean hasNext = false;
//            for (int i = 0; i < n; i++) {
//                if (i != curr) {
//                    int need = Math.abs(locations[curr] - locations[i]);
//                    if (fuel >= need) {
//                        hasNext = true;
//                        break;
//                    }
//                }
//            }
//            if (fuel != 0 && !hasNext) {
//                int a = cache[curr][fuel] = curr == finish ? 1 : 0;
//                return a;
//            }
//
//            /**
//             * 计算油量为fuel，从位置curr到end的路径数量
//             * 由于每个点都可以经过多次如果curr=end 那么本身就算一条路径
//             */
//            int sum = curr == finish ? 1 : 0;
//            for (int i = 0; i < n; i++) {
//                if (i!=curr){
//                    int need = Math.abs(locations[i] - locations[curr]);
//                    if (fuel>=need){
//                        sum+=dfs(locations,i,finish,fuel-need);
//                        sum%=mod;
//                    }
//                }
//            }
//            cache[curr][fuel] = sum;
//            return sum;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}